The optimization of a digital network is achieved by minimizing the number of logic components and connections that are required to implement the logic function of a network. A digital logic network basically consists of one or more gates or flip-flops that are interconnected by wires to form combinational or sequential circuits. Network optimization is the process of identifying those wires, gates and flip-flops that can be removed from a network, known as redundant connections or redundancies, without changing the functionality of the network. General purpose computer systems are used to perform the operative steps of network optimization.
Optimization of a network achieves a more efficient and cost effective implementation of the particular logic function of the network. The cost of synthesizing a network, in part, is related to the total number of wires, gates or flip-flops comprising a network. The removal of more and more connections and logic components from a network without changing the functionality of the network lowers the manufacturing cost associated with producing a chip which implements the particular logic function of a digital logic network.
The cost of a network is also a function of the computational cost or the amount of engineering time and computer time expended in optimizing a network. For an extremely large and complex network consisting of hundreds of thousands and even millions of connections and logic components, computational costs can attain such high levels that any cost reduction achieved by the minimization of the network is overcome by the computational cost of computer processing time expended in performing an optimization on the network and of the extended length of production time for realizing a finalized implementation of the desired logic network.
Various network optimization techniques are well known in the art. The feasibility of using any of these techniques in the synthesis of a network, therefore, depends on the extent a network is minimized by the performance of a network optimization routine and the related computational costs. For example, all possible redundancies in a network cannot be identified using the Boolean Resubstitution in the BOLD network optimization system described in D. Bostick et al., The Boulder Optimal Logic Design System, Proc. of Int'l Conf. on CAD (1987) at 62-65 and incorporated by reference herein. Other techniques well known in the art also do not provide for the identification of all redundancies in a network.
Among other well known network optimization techniques, the redundancy addition and removal (RAR) technique, first described in K. -T. Cheng and L. A. Entrena, Multi-Level Logic Optimization by Redundancy Addition and Removal, Proc. European Conf. on Design Automation (1993) at 373-77 and incorporated by reference herein, provides a most effective method for optimizing a network. RAR identifies redundant connections which can be added to a network that create a greater number of redundancies which can be removed from the network and allows for the simultaneous addition and removal of redundancies during optimization. RAR also provides a technique for multi-level minimization of sequential circuits without any restrictions in their structure.
Application of the RAR approach to the optimization of a digital network, however, also has several shortcomings. The RAR network optimization technique is implemented by the performance of redundancy testing on all connections in a network. The examination of all connections of a very large and complex network as part of an attempt to optimize the network, in most circumstances, greatly increases the computational cost for designing a network. Usually, only a very small percentage of the connections in a large and complex network are redundant and even a smaller percentage of these connections would create redundancies. Therefore, for an extremely large network, it becomes extremely complex and time consuming to determine for all possibilities whether connections should be added or not. In addition, in certain circumstances, computational costs are further aggravated by the examination of every single connection of a network because the determination of whether a network connection or a connection suggested for addition is redundant can itself be very time consuming.